import javax.swing.tree.TreeNode;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution2 {
    public int height(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1));
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        int left = height(root.left);
        int right = height(root.right);
        return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);

    }

    /*public int height(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        // return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1);
        if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1){
            return Math.max(leftHeight,rightHeight) + 1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        // int left = height(root.left);
        // int right = height(root.right);
        // return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        return height(root) >= 0;

    }*/
}

